5.7 KB · ⇊ 3 parts · ⤓ Micron 5.7 KB · ⤓ HTML 39.9 KB

top

Die Linear independence constraint qualification oder kurz LICQ ist eine wichtige Voraussetzung, dass notwendige Optimalitätskriterien in der nichtlinearen Optimierung gelten. Sie ist eine Bedingung an die Regularität eines zulässigen Punktes. Ist die LICQ in einem Punkt x ~ ~ {\displaystyle {\tilde {x}}} erfüllt und ist dieser Punkt ein lokales Minimum, so sind auch die Karush-Kuhn-Tucker-Bedingungen an diesem Punkt erfüllt.

• Definition

• Beispiel

• LICQ

• MFCQ ohne LICQ

• Vergleich mit anderen constraint qualifications

• Literatur

Gegeben ist ein Optimierungsproblem in der Form

min x ∈ ∈ X f ( x ) {\displaystyle \min _{x\in X}f(x)} ,

wobei

X = { x ∈ ∈ R n | g i ( x ) ≤ ≤ 0 , h j ( x ) = 0 , i = 1 , … … , k ; j = 1 , … … , l } {\displaystyle X=\{x\in \mathbb {R} ^{n}\,|\,g_{i}(x)\leq 0,h_{j}(x)=0,\;i=1,\dots ,k;\;j=1,\dots ,l\}}

die Restriktionsmenge ist und alle Funktionen stetig differenzierbar sein sollen. Es sei K ( x ) = { i | g i ( x ) = 0 } {\displaystyle K(x)=\{i\,|\,g_{i}(x)=0\}} die Menge der Indizes, bei denen die Ungleichungsrestriktionen mit Gleichheit erfüllt sind, d. h. die Ungleichungsrestriktion g i ( x ) {\displaystyle g_{i}(x)} ist aktiv. Dann erfüllt ein zulässiger Punkt x ~ ~ ∈ ∈ X {\displaystyle {\tilde {x}}\in X} des restringierten Optimierungsproblems die LICQ, wenn die Gradienten ∇ ∇ h j ( x ~ ~ ) {\displaystyle \nabla h_{j}({\tilde {x}})} und ∇ ∇ g i ( x ~ ~ ) {\displaystyle \nabla g_{i}({\tilde {x}})} mit i ∈ ∈ K ( x ~ ~ ) {\displaystyle i\in K({\tilde {x}})} linear unabhängig sind.

Betrachten wir als Beispiel die Restriktionsfunktionen g 1 ( x ) = x 1 + x 2 − − 1 ≤ ≤ 0 {\displaystyle g_{1}(x)=x_{1}+x_{2}-1\leq 0} und g 2 ( x ) = x 1 2 + x 2 2 − − 1 ≤ ≤ 0 {\displaystyle g_{2}(x)=x_{1}^{2}+x_{2}^{2}-1\leq 0} . Wir untersuchen, ob der Punkt x ~ ~ = ( 0 , 1 ) {\displaystyle {\tilde {x}}=(0,1)} die LICQ erfüllt. Es ist K ( x ~ ~ ) = { 1 , 2 } {\displaystyle K({\tilde {x}})=\{1,2\}} , da beide Ungleichungen in x ~ ~ {\displaystyle {\tilde {x}}} aktiv sind. Die Gradienten sind ∇ ∇ g 1 ( x ~ ~ ) = ( 1 , 1 ) T {\displaystyle \nabla g_{1}({\tilde {x}})=(1,1)^{T}} und ∇ ∇ g 2 ( x ~ ~ ) = ( 0 , 2 ) T {\displaystyle \nabla g_{2}({\tilde {x}})=(0,2)^{T}} . Beide Ungleichungsrestriktionen sind im untersuchten Punkt aktiv und die Gradienten sind linear unabhängig. Daher erfüllt der Punkt die LICQ.

Betrachtet man die Restriktionsfunktionen g 1 ( x ) = − − x 2 ≤ ≤ 0 {\displaystyle g_{1}(x)=-x_{2}\leq 0} und g 2 ( x ) = x 1 4 − − x 2 ≤ ≤ 0 {\displaystyle g_{2}(x)=x_{1}^{4}-x_{2}\leq 0} und untersucht diese im Punkt x ~ ~ = ( 0 , 0 ) {\displaystyle {\tilde {x}}=(0,0)} , so ist die LICQ nicht erfüllt. Die Gradienten ∇ ∇ g 1 ( x ~ ~ ) = ( 0 , − − 1 ) T {\displaystyle \nabla g_{1}({\tilde {x}})=(0,-1)^{T}} und ∇ ∇ g 2 ( x ~ ~ ) = ( 0 , − − 1 ) T {\displaystyle \nabla g_{2}({\tilde {x}})=(0,-1)^{T}} sind linear abhängig und beide Ungleichungen sind im untersuchten Punkt aktiv. Die MFCQ sind aber erfüllt, da für den Vektor d = ( 0 , 1 ) {\displaystyle d=(0,1)} gilt, dass ∇ ∇ g i ( x ~ ~ ) T d < 0 {\displaystyle \nabla g_{i}({\tilde {x}})^{T}d<0} .

Gilt die LICQ, so ist auch die MFCQ und daher die Abadie CQ automatisch erfüllt. Die LICQ hat im Gegensatz zur MFCQ und zur Abadie CQ den Vorteil, dass sie leicht zu überprüfen ist. Ein Nachteil ist, dass sie nicht so allgemein gültig ist wie die anderen constraint qualifications. Dies wird durch das obige Beispiel illustriert. Es gelten die Implikationen

LICQ ⟹ ⟹ MFCQ ⟹ ⟹ Abadie CQ {\displaystyle {\text{LICQ}}\implies {\text{MFCQ}}\implies {\text{Abadie CQ}}} .

Die Umkehrungen gelten aber nicht.

• C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002. ISBN 3-540-42790-2. https://books.google.de/books?id=spmzFyso_b8C&hl=de